L2 Network 10
An L2 network (abbreviated-network) is composed of L2 bridges (a.k.a., L2 switches) connecting local area networks (LAN) or IEEE 802.1Q virtual LAN (VLAN) segments containing end stations. A switch forwards L2 frames (packets) between its interfaces (ports) based on L2 media access control destination address (MAC DA) carried by each packet. A switch performs address learning based on L2 MAC source address (MAC SA) carried by each packet. This procedure is also called MAC learning. If a switch receives a packet with a known unicast DA (i.e., one it has previously learned as SA), it would forward the packet to the port from which it learned the address. Otherwise, if the DA is unknown unicast (has not been learned) or multi-destination (multicast or broadcast), it would forward a packet copy to all the ports, this action is referred to as flooding. A port may belong to multiple LANs, known as virtual LANs (VLANs), in which case the address learning and forwarding is based on L2 address combined with VLANs carried by the packets.
In addition, the provider may map the customer traffic into Provider Service VLANs (SVLANs) using VLAN stacking techniques (so called Q-in-Q encapsulation) in order to partition traffic of one customer from another. Such networks are called provider bridge (PB) networks.
VPLS
A virtual private LAN service (VPLS) emulates the functionality of a LAN making it possible to interconnect multiple access networks over a VPLS network while all these access networks together behave as one single LAN or virtual LAN (VLAN). With VPLS, all these access networks would be assigned the same L2 virtual private network (L2 VPN or VPN) identifier. This is analogous to assigning them the same SVLAN in an Ethernet-based provider network. For convenience, we will refer to both SVLAN and VPLS instances as VPNs.
VPLS networks generally perform better than PB networks. With VPLS, Ethernet packets arriving from the access network are encapsulated in multi-protocol label switching (MPLS), based on which they are forwarded across the provider network towards the remote sites. This use of MPLS enables to build networks that excel in performance, quality of service (QoS) for service differentiation, traffic engineering (TE) for optimal utilization of network resources, high resiliency (particularly fast rerouting, FRR), and high scalability.
VPLS architecture implements full mesh connectivity between the provider edge (PE) nodes that connect the customer access networks, this allows each access network to communicate with any other access network belonging to the same VPN. Each PE-PE path carrying VPN traffic is called a pseudo-wire (PW).
Since there is a PW between any two PEs, a PE receiving a packet from PW must not forward it on another PW, otherwise the destination PE might receive two packet copies. This is referred to as a split horizon rule.
As an alternative to using Ethernet-VLAN for connecting networks is to classify customer traffic to specific VPN, the connection is so-called spoke pseudowire (spoke PW or just spoke). With this method, known as hierarchical VPLS (H-VPLS), Ethernet packets already arrive encapsulated with MPLS headers over the connection to the provider network. Spoke PWs are generally not subject to the split horizon rule, i.e., a PE receiving a packet from VPLS PW can forward it on spoke PW and vice versa. H-VPLS is potentially preferred over either Ethernet or VLAN (Ethernet-VLAN) owing to its MPLS advantages.
It should be understood that an H-VPLS spoke carries traffic of a single VPN. If multiple VPNs are needed per link between networks, each VPN would have its own H-VPLS spoke flowing in parallel with the other spokes.
Dual Homing
An important if not mandatory feature in packet-based applications is effective redundancy, which enables fault-tolerant and reliable networks. One form of fault tolerant connectivity is the so-called dual homing. With dual homing configuration, a device or a network is connected to another device or network via two connections, such that when one connection fails the other one serves for carrying the traffic. Dual homing can either be partially redundant or fully redundant. Both of the dual homing forms use two connections between the L2 gateway (GW) devices, however only the fully redundant dual homing protects against any single link or GW failure at the interconnection.
Dual homing switchover would generally require the flushing (a.k.a., MAC flush) the forwarding information base (FIB) holding the L2 addresses learned, once the new GW takes over, since otherwise other nodes in the network might continue sending the known unicast traffic to the previous GW who is presumably down, until a periodic (typically 5 minute period) address aging occurs. After the flush occurs at a network node, it would flood L2 traffic thus reaching all destinations until address learning takes place. The address flushing is generally performed per VPN and is achievable using dedicated messaging, such as the LDP Address Withdraw Message (RFC 4762), or the Customer Change Notification (CCN) defined at draft-ietf-12vpn-vpls-bridge-interop-04.txt. The spanning tree protocol (STP) and its variants (RSTP, MSTP), all of which are hereby referred to as xSTP, have a built-in MAC flush mechanism applied following a topology change. All the address flushing messages are hereby referred to as CCN messages. The detriment of CCN is the subsequent flooding of traffic, which may overload the network nodes, and result with considerable traffic loss.
Dual homing configurations are illustrated in FIG. 1 (Prior art):                Configuration A is partially redundant, because when GW PE1 or PE2 fails, the connectivity between network 1 and network 2 is lost        Configuration B is partially redundant, because when GW PE3 fails, the connectivity between network 3 and network 4 is lost        Configuration C is fully redundant, because for any single link (either link PE6-PE8 or link PE7-PE9 or single GW (either of PE6, PE7, PE8, or PE9) failure, the connectivity between network 5 and network 6 could remain intact.        CCN messaging is required at network 4 when PE5 takes over PE4. This is required in order that PEa would stop sending known unicast traffic to network 3 through the failed PE4. Similarly, CCN messaging is required when PE4 takes over PE5.        CCN messaging is required at both networks 5 and 6 when PE7 takes over PE6. This is required in order that PEb (PEc) would stop sending known unicast traffic to network 6 (network 5) through the failed PE6, respectively. Similarly, CCN messaging is required when PE6 takes over PE7, or when PE8 takes over PE9 or vice versa.        
While dual homing can improve network reliability, its application is not straightforward. If two networks are connected via dual homing where both connections are active, a L2 loop occurs. Multicast or broadcast traffic introduced into dual homed connection, might keep circulating indefinitely between the connected networks. Assuring loop-free topology is therefore essential to proper operation of Ethernet networks. Without a proper dual homing, H-VPLS benefits would be rendered impractical.
Prior Art solutions
The methods referred to below are analyzed from the point of satisfying a number of main conditions/objectives stated by the Inventor, wherein the objectives are listed in the section of Object and Summary of the invention (since most of them comprise inventive subject matter)
There have been proposed several methods for dual homed connectivity between devices and networks:
(1) IETF RFC 4762, section 10.2.1 (VPLS standard) proposes a partially redundant dual homing, where the dual homed device forces one of the dual homing connections to a standby mode, during which it does not actively carry traffic.
“To protect from connection failure of the PW or the failure of the PE-rs, the MTU-s or the PE-r is dual-homed into two PE-rs devices . . . The MTU-s negotiates the PW labels for both the Primary and Secondary PWs, but does not use the Secondary PW unless the Primary PW fails.”
It further does not propose any form of redundancy for connecting VPLS networks via H-VPLS:
“Two fully meshed VPLS networks are connected together using a single LSP tunnel between the VPLS “border” devices. A single spoke PW per VPLS service is set up to connect the two domains together . . . . This document does not specify how redundant border PEs per domain per VPLS instance can be supported.”
In summary, this approach does not support the fully redundant dual homing (the Primary objective-A1-of full redundancy).
(2) draft-ietf-pwe3-redundancy-01.txt is aligned with RFC 4762 described above, and only addresses a partially redundant dual homing. This is exemplified by FIG. 1 there, where a single CE device is dual homed with two AC connections to the PW-based network. If CE device were part of a CE network, that network would be disconnected from the PW-based network once the CE device failed.
In summary, this approach also does not support fully redundant dual homing (the Primary objective A1).
(3)http://www.alcatel.com/doctypes/opgapplicationbrochure/pdf/Resilient_HVPLS_a n.pdf (hereby referred to as Alcatel's), achieves fully redundant H-VPLS connectivity between networks using xSTP. A drawback of this method is the need to maintain xSTP (along with its built-in CCN) interaction among the GWs of the different networks. This is especially complicated when the dual homing connectivity is created between two networks running under different administrations, due to the xSTP provisioning and maintenance burden it inflicts upon the parties involved.
In summary, this approach does not confine the protocol to the two local GWs (objective A2), cannot work with mixed network configurations (A3), does not confine the CCN to the local network (A4), and uses xSTP (A5).
(4) US 2006/0047851 (further referred as Cisco's) proposes a method in which a local node u-PE is dual homed to two local nodes Agg-PEs and can communicate with remote nodes u-PE in a loop-free manner, wherein all of the involved local/remote u-PEs and Agg-PEs run a common xSTP protocol in order to break the L2 loop. This method uses xSTP between the u-PE and Agg-PE, wherein the (xSTP) signaling is not a local matter on the border of the two connected networks, since it involves both the local and remote u-PEs and Agg-PEs.
In summary, this approach does not confine the protocol to the two local GWs (objective A2), cannot work with mixed network configurations (A3), does not confine the CCN to the local network (A4), and uses xSTP (A5)
(5) http://www.cisco.com/en/US/docs/ios/mpls/configuration/guide/mp_hvpls_npe_re d.html#wp1054360 (further referred as Cisco's website) describes two configurations: (a) One configuration provides partially redundant dual homing when connecting networks with H-VPLS (FIG. 2 there), as when U-PE fails the connectivity to the network represented by N-PE1 through N-PE4 is lost. This configuration therefore fails to address the Primary objective A1; (b) Another configuration runs xSTP (along with its built-in CCN) between the access network (U-PE) and the aggregate network (N-PEs) to provide partially redundant dual homing when connecting networks with Q-in-Q (FIG. 1 there). Though there are two U-PEs in the picture, there is actually a single U-PE per VLAN (VPN), thus no full redundancy. This configuration therefore fails to address the Primary objective A1. It further does not confine the protocol to the two local GWs (objective A2), cannot work with mixed network configurations (A3), does not confine the CCN to the local network (A4), and uses xSTP (A5).
(6) EP2027676 A1 (US2009274155 AA, Technique for Providing Interconnection between Communication Networks proposes an approach that provides a fully redundant dual homing. It meets objectives A1 for fully redundant dual homing, A2 for local protocol per network, A3 for mixed networks capability, A5 for protocol simplicity, and A7 for protection time. However, this solution fails to address: (a) A4 and B3, because the CCN must be propagated to 3rd party network as well as the GWs of the remote networks; (b) A8, because a GW must run a separate protocol instance per each physical link it uses to connect to 3rd party network; (c) B4, because there is a need for a full mesh of 3rd party pipes between any two connected networks. This is so because each network independently selects the active GW (designated forwarder, or Primary node), and when it fails the other one would take over and should have a pipe per each of the GWs of the remote network, as only one GW per remote network is presumably active; (d) B5, because 3rd party connections should be protected.